home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 52 / Amiga Format AFCD52 (Issue 136, May 2000).iso / -serious- / programming / other / jikes-1.11 / src / lookup.cpp < prev    next >
C/C++ Source or Header  |  2000-02-23  |  49KB  |  1,777 lines
  1. // $Id: lookup.cpp,v 1.21 1999/11/18 03:37:23 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "config.h"
  11. #include <iostream.h>
  12. #include "control.h"
  13. #include "lookup.h"
  14. #include "symbol.h"
  15. #include "code.h"
  16. #include "ast.h"
  17. #include "case.h"
  18.  
  19. int SystemTable::primes[] = {DEFAULT_HASH_SIZE, 101, 401, MAX_HASH_SIZE};
  20.  
  21. SystemTable::SystemTable(int hash_size_) : directories(1024)
  22. {
  23.     hash_size = (hash_size_ <= 0 ? 1 : hash_size_);
  24.  
  25.     prime_index = -1;
  26.     do
  27.     {
  28.         if (hash_size < primes[prime_index + 1])
  29.             break;
  30.         prime_index++;
  31.     } while (primes[prime_index] < MAX_HASH_SIZE);
  32.  
  33.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  34. }
  35.  
  36. SystemTable::~SystemTable()
  37. {
  38.     for (int i = 0; i < directories.Length(); i++)
  39.         delete directories[i];
  40. }
  41.  
  42. void SystemTable::Rehash()
  43. {
  44.     hash_size = primes[++prime_index];
  45.  
  46.     delete [] base;
  47.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  48.  
  49.     for (int k = 0; k < directories.Length(); k++)
  50.     {
  51.         Element *element = directories[k];
  52.  
  53.         int i = hash(element -> device, element -> inode);
  54.         element -> next = base[i];
  55.         base[i] = element;
  56.     }
  57.  
  58.     return;
  59. }
  60.  
  61. DirectorySymbol *SystemTable::FindDirectorySymbol(dev_t device, ino_t inode)
  62. {
  63.     int k = hash(device, inode);
  64.  
  65.     for (Element *element = base[k]; element; element = element -> next)
  66.     {
  67.         if (element -> device == device && element -> inode == inode)
  68.             return element -> directory_symbol;
  69.     }
  70.  
  71.     return NULL;
  72. }
  73.  
  74. void SystemTable::InsertDirectorySymbol(dev_t device, ino_t inode, DirectorySymbol *directory_symbol)
  75. {
  76.     int k = hash(device, inode);
  77.  
  78.     Element *element = new Element(device, inode, directory_symbol);
  79.     directories.Next() = element;
  80.  
  81.     element -> next = base[k];
  82.     base[k] = element;
  83.  
  84.     //
  85.     // If the set is "adjustable" and the number of unique elements in it exceeds
  86.     // 2 times the size of the base, and we have not yet reached the maximum
  87.     // allowable size for a base, reallocate a larger base and rehash the elements.
  88.     //
  89.     if ((directories.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  90.         Rehash();
  91.  
  92.     return;
  93. }
  94.  
  95. int DirectoryTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  96.  
  97. DirectoryTable::DirectoryTable(int estimate) : entry_pool(estimate),
  98.                                                hash_size(primes[0]),
  99.                                                prime_index(0)
  100. {
  101.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  102. }
  103.  
  104. DirectoryTable::~DirectoryTable()
  105. {
  106. /*
  107. int n;
  108. int num_slots = 0;
  109. int total = 0;
  110. for (n = 0; n < hash_size; n++)
  111. {
  112. int num = 0;
  113. for (Symbol *s = base[n]; s; s = s -> next)
  114.     num++;
  115. if (num > 0)
  116. {
  117. num_slots++;
  118. total += num;
  119. }
  120. }
  121.  
  122. if (num_slots > 0)
  123. {
  124. Coutput << "\nDestroying the Name table with " << total
  125.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  126. for (n = 0; n < hash_size; n++)
  127. {
  128. int num = 0;
  129. for (Symbol *s = base[n]; s; s = s -> next)
  130.     num++;
  131. if (num > 0)
  132. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  133. }
  134. }
  135. if (hash_size < total)
  136.     total = total;
  137. */
  138. #ifdef TEST
  139.     for (int i = 0; i < entry_pool.Length(); i++)
  140.         delete entry_pool[i];
  141.     delete [] base;
  142. #endif
  143. }
  144.  
  145.  
  146. DirectoryEntry *DirectoryTable::FindEntry(char *str, int len)
  147. {
  148.     int k = Hash(str, len) % hash_size;
  149.     DirectoryEntry *entry;
  150.     for (entry = base[k]; entry; entry = entry -> next)
  151.     {
  152.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  153.             return (entry -> IsDummy() ? (DirectoryEntry *) NULL : entry);
  154.     }
  155.  
  156.     return NULL;
  157. }
  158.  
  159.  
  160. void DirectoryTable::Rehash()
  161. {
  162.     hash_size = primes[++prime_index];
  163.  
  164.     delete [] base;
  165.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  166.  
  167.     for (int i = 0; i < entry_pool.Length(); i++)
  168.     {
  169.         DirectoryEntry *e = entry_pool[i];
  170.         int k = Hash(e -> name, e -> length) % hash_size;
  171.         e -> next = base[k];
  172.         base[k] = e;
  173.     }
  174.  
  175.     return;
  176. }
  177.  
  178.  
  179. DirectoryEntry *DirectoryTable::InsertEntry(DirectorySymbol *directory_symbol, char *str, int len)
  180. {
  181.     int k = Hash(str, len) % hash_size;
  182.     DirectoryEntry *entry;
  183.     for (entry = base[k]; entry; entry = entry -> next)
  184.     {
  185.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  186.             return entry;
  187.     }
  188.  
  189.     entry = new DirectoryEntry();
  190.     entry_pool.Next() = entry;
  191.     entry -> Initialize(directory_symbol, str, len);
  192.  
  193.     entry -> next = base[k];
  194.     base[k] = entry;
  195.  
  196.     //
  197.     // If the number of unique elements in the hash table exceeds 2 times
  198.     // the size of the base, and we have not yet reached the maximum
  199.     // allowable size for a base, reallocate a larger base and rehash
  200.     // the elements.
  201.     //
  202.     if ((entry_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  203.         Rehash();
  204.  
  205.     return entry;
  206. }
  207.  
  208.  
  209. #ifdef WIN32_FILE_SYSTEM
  210. DirectoryEntry *DirectoryTable::FindCaseInsensitiveEntry(char *name, int length)
  211. {
  212.     char *lower_name = new char[length + 1];
  213.     for (int i = 0; i < length; i++)
  214.         lower_name[i] = Case::ToAsciiLower(name[i]);
  215.     lower_name[length] = U_NULL;
  216.  
  217.     DirectoryEntry *entry = FindEntry(lower_name, length);
  218.     delete [] lower_name;
  219.  
  220.     return (entry ? entry -> Image() : entry);
  221. }
  222.  
  223. void DirectoryTable::InsertCaseInsensitiveEntry(DirectoryEntry *image)
  224. {
  225.     int length = image -> length;
  226.     char *lower_name = new char[length + 1];
  227.     for (int i = 0; i < length; i++)
  228.         lower_name[i] = Case::ToAsciiLower(image -> name[i]);
  229.     lower_name[length] = U_NULL;
  230.  
  231.     int k = Hash(lower_name, length) % hash_size;
  232.     DirectoryEntry *entry;
  233.     for (entry = base[k]; entry; entry = entry -> next)
  234.     {
  235.         if (length == entry -> length && memcmp(entry -> name, lower_name, length * sizeof(char)) == 0)
  236.             break;
  237.     }
  238.  
  239.     if (! entry)
  240.     {
  241.         FoldedDirectoryEntry *folded_entry = new FoldedDirectoryEntry(image);
  242.         entry_pool.Next() = folded_entry;
  243.         folded_entry -> Initialize(image, lower_name, length);
  244.  
  245.         folded_entry -> next = base[k];
  246.         base[k] = folded_entry;
  247.  
  248.         //
  249.         // If the number of unique elements in the hash table exceeds 2 times
  250.         // the size of the base, and we have not yet reached the maximum
  251.         // allowable size for a base, reallocate a larger base and rehash
  252.         // the elements.
  253.         //
  254.         if ((entry_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  255.             Rehash();
  256.     }
  257.  
  258.     delete [] lower_name;
  259.  
  260.     return;
  261. }
  262. #endif
  263.  
  264.  
  265. time_t DirectoryEntry::Mtime()
  266. {
  267.     if (mtime_ == 0)
  268.     {
  269.         char *dirname = this -> directory -> DirectoryName();
  270.         int length = this -> directory -> DirectoryNameLength() + this -> length + 1; // +1 for '/'
  271.         char *file_name = new char[length + 1];
  272.         strcpy(file_name, dirname);
  273.         if (dirname[this -> directory -> DirectoryNameLength() - 1] != U_SLASH)
  274.             strcat(file_name, StringConstant::U8S__SL);
  275.         strcat(file_name, this -> name);
  276.  
  277.         struct stat status;
  278.         if (::SystemStat(file_name, &status) == 0)
  279.              mtime_ = status.st_mtime;
  280.         else assert(false && "Cannot compute system time stamp\n");
  281.  
  282.         delete [] file_name;
  283.     }
  284.  
  285.     return mtime_;
  286. }
  287.  
  288.  
  289. int NameLookupTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  290.  
  291. NameLookupTable::NameLookupTable(int estimate) : symbol_pool(estimate),
  292.                                                  hash_size(primes[0]),
  293.                                                  prime_index(0)
  294. {
  295.     base = (NameSymbol **) memset(new NameSymbol *[hash_size], 0, hash_size * sizeof(NameSymbol *));
  296. }
  297.  
  298. NameLookupTable::~NameLookupTable()
  299. {
  300. /*
  301. int n;
  302. int num_slots = 0;
  303. int total = 0;
  304. for (n = 0; n < hash_size; n++)
  305. {
  306. int num = 0;
  307. for (Symbol *s = base[n]; s; s = s -> next)
  308.     num++;
  309. if (num > 0)
  310. {
  311. num_slots++;
  312. total += num;
  313. }
  314. }
  315.  
  316. if (num_slots > 0)
  317. {
  318. Coutput << "\nDestroying the Name table with " << total
  319.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  320. for (n = 0; n < hash_size; n++)
  321. {
  322. int num = 0;
  323. for (Symbol *s = base[n]; s; s = s -> next)
  324.     num++;
  325. if (num > 0)
  326. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  327. }
  328. }
  329. if (hash_size < total)
  330.     total = total;
  331. */
  332. #ifdef TEST
  333.     for (int i = 0; i < symbol_pool.Length(); i++)
  334.         delete symbol_pool[i];
  335.     delete [] base;
  336. #endif
  337. }
  338.  
  339.  
  340. void NameLookupTable::Rehash()
  341. {
  342.     hash_size = primes[++prime_index];
  343.  
  344.     delete [] base;
  345.     base = (NameSymbol **) memset(new NameSymbol *[hash_size], 0, hash_size * sizeof(NameSymbol *));
  346.  
  347.     for (int i = 0; i < symbol_pool.Length(); i++)
  348.     {
  349.         NameSymbol *ns = symbol_pool[i];
  350.         int k = ns -> hash_address % hash_size;
  351.         ns -> next = base[k];
  352.         base[k] = ns;
  353.     }
  354.  
  355.     return;
  356. }
  357.  
  358.  
  359. NameSymbol *NameLookupTable::FindOrInsertName(wchar_t *str, size_t len)
  360. {
  361.     unsigned hash_address = Hash(str, len);
  362.     int k = hash_address % hash_size;
  363.     NameSymbol *symbol;
  364.     for (symbol = base[k]; symbol; symbol = (NameSymbol *) symbol -> next)
  365.     {
  366.         if (len == symbol -> NameLength() && memcmp(symbol -> Name(), str, len * sizeof(wchar_t)) == 0)
  367.             return symbol;
  368.     }
  369.  
  370.     int index = symbol_pool.Length(); // index of the next element
  371.     symbol = new NameSymbol();
  372.     symbol_pool.Next() = symbol;
  373.     symbol -> Initialize(str, len, hash_address, index);
  374.  
  375.     symbol -> next = base[k];
  376.     base[k] = symbol;
  377.  
  378.     //
  379.     // If the number of unique elements in the hash table exceeds 2 times
  380.     // the size of the base, and we have not yet reached the maximum
  381.     // allowable size for a base, reallocate a larger base and rehash
  382.     // the elements.
  383.     //
  384.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  385.         Rehash();
  386.  
  387.     return symbol;
  388. }
  389.  
  390.  
  391. int TypeLookupTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  392.  
  393. TypeLookupTable::TypeLookupTable(int estimate) : symbol_pool(estimate),
  394.                                                  hash_size(primes[0]),
  395.                                                  prime_index(0)
  396. {
  397.     base = (TypeSymbol **) memset(new TypeSymbol *[hash_size], 0, hash_size * sizeof(TypeSymbol *));
  398. }
  399.  
  400.  
  401. TypeLookupTable::~TypeLookupTable()
  402. {
  403. /*
  404. int n;
  405. int num_slots = 0;
  406. int total = 0;
  407. for (n = 0; n < hash_size; n++)
  408. {
  409. int num = 0;
  410. for (TypeSymbol *s = base[n]; s; s = s -> next_type)
  411.     num++;
  412. if (num > 0)
  413. {
  414. num_slots++;
  415. total += num;
  416. }
  417. }
  418.  
  419. if (num_slots > 0)
  420. {
  421. Coutput << "\nDestroying the Type table with " << total
  422.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  423. for (n = 0; n < hash_size; n++)
  424. {
  425. int num = 0;
  426. for (TypeSymbol *s = base[n]; s; s = s -> next_type)
  427.     num++;
  428. if (num > 0)
  429. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  430. }
  431. }
  432. if (hash_size < total)
  433.     total = total;
  434. */
  435.  
  436. #ifdef TEST
  437.     delete [] base;
  438. #endif
  439. }
  440.  
  441.  
  442. void TypeLookupTable::Rehash()
  443. {
  444.     hash_size = primes[++prime_index];
  445.  
  446.     delete [] base;
  447.     base = (TypeSymbol **) memset(new TypeSymbol *[hash_size], 0, hash_size * sizeof(TypeSymbol *));
  448.  
  449.     for (int i = 0; i < symbol_pool.Length(); i++)
  450.     {
  451.         TypeSymbol *type = symbol_pool[i];
  452.         int k = type -> hash_address % hash_size;
  453.         type -> next_type = base[k];
  454.         base[k] = type;
  455.     }
  456.  
  457.     return;
  458. }
  459.  
  460.  
  461. TypeSymbol *TypeLookupTable::FindType(char *str, int len)
  462. {
  463.     unsigned hash_address = Hash(str, len);
  464.     int k = hash_address % hash_size;
  465.  
  466.     for (TypeSymbol *type = base[k]; type; type = type -> next_type)
  467.     {
  468.         assert(type -> fully_qualified_name);
  469.  
  470.         Utf8LiteralValue *fully_qualified_name = type -> fully_qualified_name;
  471.         if (len == fully_qualified_name -> length && memcmp(fully_qualified_name -> value, str, len * sizeof(char)) == 0)
  472.             return type;
  473.     }
  474.  
  475.     return NULL;
  476. }
  477.  
  478.  
  479. void TypeLookupTable::InsertType(TypeSymbol *type)
  480. {
  481.     assert(type && type -> fully_qualified_name);
  482.  
  483.     unsigned hash_address = Hash(type -> fully_qualified_name -> value, type -> fully_qualified_name -> length);
  484.     int k = hash_address % hash_size;
  485.  
  486. #ifdef TEST
  487.     for (TypeSymbol *t = base[k]; t; t = t -> next_type)
  488.         assert (type != t && "Type was already entered in type table");
  489. #endif
  490.  
  491.     symbol_pool.Next() = type;
  492.     type -> hash_address = hash_address;
  493.  
  494.     type -> next_type = base[k];
  495.     base[k] = type;
  496.  
  497.     //
  498.     // If the number of unique elements in the hash table exceeds 2 times
  499.     // the size of the base, and we have not yet reached the maximum
  500.     // allowable size for a base, reallocate a larger base and rehash
  501.     // the elements.
  502.     //
  503.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  504.         Rehash();
  505.  
  506.     return;
  507. }
  508.  
  509.  
  510. //
  511. // Remove all elements from the table.
  512. //
  513. void TypeLookupTable::SetEmpty()
  514. {
  515.     symbol_pool.Reset();
  516.     (void) memset(base, 0, hash_size * sizeof(TypeSymbol *));
  517. }
  518.  
  519.  
  520. int IntLiteralTable::int32_limit = 0x7FFFFFFF / 10;
  521. int IntLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  522.  
  523. IntLiteralTable::IntLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  524.                                                              hash_size(primes[0]),
  525.                                                              prime_index(0),
  526.                                                              bad_value(bad_value_)
  527. {
  528.     base = (IntLiteralValue **) memset(new IntLiteralValue *[hash_size], 0, hash_size * sizeof(IntLiteralValue *));
  529.     symbol_pool.Next() = NULL; // do not use the 0th element
  530. }
  531.  
  532. IntLiteralTable::~IntLiteralTable()
  533. {
  534. /*
  535. int n;
  536. int num_slots = 0;
  537. int total = 0;
  538. for (n = 0; n < hash_size; n++)
  539. {
  540. int num = 0;
  541. for (LiteralValue *s = base[n]; s; s = s -> next)
  542.     num++;
  543. if (num > 0)
  544. {
  545. num_slots++;
  546. total += num;
  547. }
  548. }
  549.  
  550. if (num_slots > 0)
  551. {
  552. Coutput << "\nDestroying the integer table with " << total
  553.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  554. for (n = 0; n < hash_size; n++)
  555. {
  556. int num = 0;
  557. for (LiteralValue *s = base[n]; s; s = s -> next)
  558.     num++;
  559. if (num > 0)
  560. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  561. }
  562. }
  563. if (hash_size < total)
  564.     total = total;
  565. */
  566.  
  567. #ifdef TEST
  568.     for (int i = 0; i < symbol_pool.Length(); i++)
  569.         delete symbol_pool[i];
  570.     delete [] base;
  571. #endif
  572. }
  573.  
  574.  
  575. LiteralValue *IntLiteralTable::FindOrInsertChar(LiteralSymbol *literal)
  576. {
  577.     wchar_t *name = literal -> Name();
  578.  
  579.     if (literal -> NameLength() == 1) // an isolated quote
  580.          return literal -> value = bad_value;
  581.     else if (literal -> NameLength() <= 3) // a regular character of the form:  quote + char
  582.                                            // or                                quote + char + quote
  583.          return literal -> value = FindOrInsert((int) name[1]);
  584.  
  585.     int value;
  586.  
  587.     if (name[1] != U_BACKSLASH)
  588.          value = -1;
  589.     else if (name[2] == U_b && name[3] == U_SINGLE_QUOTE)
  590.          value = U_BACKSPACE;
  591.     else if (name[2] == U_t && name[3] == U_SINGLE_QUOTE)
  592.          value = U_HORIZONTAL_TAB;
  593.     else if (name[2] == U_n && name[3] == U_SINGLE_QUOTE)
  594.          value = U_LINE_FEED;
  595.     else if (name[2] == U_f && name[3] == U_SINGLE_QUOTE)
  596.          value = U_FORM_FEED;
  597.     else if (name[2] == U_r && name[3] == U_SINGLE_QUOTE)
  598.          value = U_CARRIAGE_RETURN;
  599.     else if (name[2] == U_DOUBLE_QUOTE && name[3] == U_SINGLE_QUOTE)
  600.          value = U_DOUBLE_QUOTE;
  601.     else if (name[2] == U_SINGLE_QUOTE && name[3] == U_SINGLE_QUOTE)
  602.          value = U_SINGLE_QUOTE;
  603.     else if (name[2] == U_BACKSLASH && name[3] == U_SINGLE_QUOTE)
  604.          value = U_BACKSLASH;
  605.     else if (Code::IsDigit(name[2]))
  606.     {
  607.         wchar_t *p = &name[2];
  608.  
  609.         int d1 = *p++ - U_0;
  610.         value = (d1 < 8 ? d1 : -1);
  611.  
  612.         if (value >= 0 && Code::IsDigit(*p))
  613.         {
  614.             int d2 = *p++ - U_0;
  615.             value = (d2 < 8 ? value * 8 + d2 : -1);
  616.  
  617.             if (value >= 0 && Code::IsDigit(*p))
  618.             {
  619.                 int d3 = *p++ - U_0;
  620.                 value = (d3 < 8 && d1 < 4 ? value * 8 + d3 : -1);
  621.             }
  622.         }
  623.  
  624.         if (*p != U_NULL && *p != U_SINGLE_QUOTE)
  625.             value = -1;
  626.     }
  627.     else value = -1;
  628.  
  629.     return literal -> value = (value < 0 || value > 65535 ? bad_value : FindOrInsert(value));
  630. }
  631.  
  632.  
  633. LiteralValue *IntLiteralTable::FindOrInsertHexInt(LiteralSymbol *literal)
  634. {
  635.     wchar_t *head = literal -> Name() + 1, // point to X
  636.             *tail = &literal -> Name()[literal -> NameLength() - 1];
  637.  
  638.     u4 uvalue = 0;
  639.  
  640.     //
  641.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  642.     // hexadecimal or octal int literal does not fit in 32 bits".
  643.     // So, strictly speaking, we should not skip leading zeroes. However,
  644.     // there are many publicly available code out there with leading zeroes
  645.     // that don't compile with jikes, if ...
  646.     //
  647.     {
  648.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  649.             ;
  650.         head--;
  651.     }
  652.  
  653.     for (int i = 0; i < 32 && tail > head; i += 4, tail--)
  654.     {
  655.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  656.         uvalue |= (d << i);
  657.     }
  658.  
  659.     return (tail > head ? bad_value : FindOrInsert((int) uvalue));
  660. }
  661.  
  662.  
  663. LiteralValue *IntLiteralTable::FindOrInsertOctalInt(LiteralSymbol *literal)
  664. {
  665.     wchar_t *head = literal -> Name(), // point to initial '0'
  666.             *tail = &head[literal -> NameLength() - 1];
  667.  
  668.     u4 uvalue = 0;
  669.     //
  670.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  671.     // hexadecimal or octal int literal does not fit in 32 bits".
  672.     // So, strictly speaking, we should not skip leading zeroes. However,
  673.     // there are many publicly available code out there with leading zeroes
  674.     // that don't compile with jikes,...
  675.     //
  676.     {
  677.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  678.             ;
  679.         head--;
  680.     }
  681.  
  682.     for (int i = 0; i < 30 && tail > head; i += 3, tail--)
  683.     {
  684.         u4 d = *tail - U_0;
  685.         uvalue |= (d << i);
  686.     }
  687.  
  688.     if (tail > head)
  689.     {
  690.         u4 d = *tail - U_0;
  691.  
  692.         if (d <= 3) // max number that can fit in 2 bits
  693.         {
  694.             tail--;
  695.             uvalue |= (d << 30);
  696.         }
  697.     }
  698.  
  699.     return (tail > head ? bad_value : FindOrInsert((int) uvalue));
  700. }
  701.  
  702.  
  703. LiteralValue *IntLiteralTable::FindOrInsertInt(LiteralSymbol *literal)
  704. {
  705.     wchar_t *name = literal -> Name();
  706.  
  707.     if (name[0] == U_0)
  708.         literal -> value = (name[1] == U_x || name[1] == U_X ? FindOrInsertHexInt(literal) : FindOrInsertOctalInt(literal));
  709.     else
  710.     {
  711.         int value = 0;
  712.  
  713.         wchar_t *p;
  714.         for (p = name; *p; p++)
  715.         {
  716.             int digit = *p - U_0;
  717.             if (value > int32_limit || (value == int32_limit && digit > 7))
  718.                 break;
  719.             value = value * 10 + digit;
  720.         }
  721.  
  722.         literal -> value = (*p ? bad_value : FindOrInsert(value));
  723.     }
  724.  
  725.     return literal -> value;
  726. }
  727.  
  728.  
  729. LiteralValue *IntLiteralTable::FindOrInsertNegativeInt(LiteralSymbol *literal)
  730. {
  731.     if (literal -> value && literal -> value != bad_value) // a positive value already exists
  732.     {
  733.         IntLiteralValue *int_literal = (IntLiteralValue *) literal -> value;
  734.         return FindOrInsert(- int_literal -> value);
  735.     }
  736.  
  737.     wchar_t *name = literal -> Name();
  738.  
  739.     //
  740.     // We can assert that the name of a literal contains at least two characters:
  741.     // at least one digit and the terminating '\0'.
  742.     //
  743.     if (name[0] == U_0)
  744.     {
  745.         IntLiteralValue *int_literal = (IntLiteralValue *) (name[1] == U_x || name[1] == U_X
  746.                                                                      ? FindOrInsertHexInt(literal)
  747.                                                                      : FindOrInsertOctalInt(literal));
  748.         return FindOrInsert(- int_literal -> value);
  749.     }
  750.  
  751.     int value = 0;
  752.  
  753.     wchar_t *p;
  754.     for (p = name; *p; p++)
  755.     {
  756.         int digit = *p - U_0;
  757.         if (value > int32_limit || (value == int32_limit && digit > 8))
  758.             break;
  759.         value = value * 10 + digit;
  760.     }
  761.  
  762.     return (*p ? bad_value : FindOrInsert(-value));
  763. }
  764.  
  765.  
  766. void IntLiteralTable::Rehash()
  767. {
  768.     hash_size = primes[++prime_index];
  769.  
  770.     delete [] base;
  771.     base = (IntLiteralValue **) memset(new IntLiteralValue *[hash_size], 0, hash_size * sizeof(IntLiteralValue *));
  772.  
  773.     //
  774.     // Recall that the 0th element is unused.
  775.     //
  776.     for (int i = 1; i < symbol_pool.Length(); i++)
  777.     {
  778.         IntLiteralValue *ilv = symbol_pool[i];
  779.         int k = ((unsigned) ilv -> value) % hash_size; // The unsigned casting turns the negative values into positive values
  780.         ilv -> next = base[k];
  781.         base[k] = ilv;
  782.     }
  783.  
  784.     return;
  785. }
  786.  
  787.  
  788. IntLiteralValue *IntLiteralTable::Find(int value)
  789. {
  790.     int k = ((unsigned) value) % hash_size; // The unsigned casting turns the negative values into positive values
  791.  
  792.     IntLiteralValue *lit = NULL;
  793.     for (lit = base[k]; lit; lit = (IntLiteralValue *) lit -> next)
  794.     {
  795.         if (lit -> value == value)
  796.             break;
  797.     }
  798.  
  799.     return lit;
  800. }
  801.  
  802.  
  803. IntLiteralValue *IntLiteralTable::FindOrInsert(int value)
  804. {
  805.     int k = ((unsigned) value) % hash_size; // The unsigned casting turns the negative values into positive values
  806.  
  807.     IntLiteralValue *lit;
  808.     for (lit = base[k]; lit; lit = (IntLiteralValue *) lit -> next)
  809.     {
  810.         if (lit -> value == value)
  811.             return lit;
  812.     }
  813.  
  814.     lit = new IntLiteralValue();
  815.     lit -> Initialize(value, symbol_pool.Length());
  816.     symbol_pool.Next() = lit;
  817.  
  818.     lit -> next = base[k];
  819.     base[k] = lit;
  820.  
  821.     //
  822.     // If the number of unique elements in the hash table exceeds 2 times
  823.     // the size of the base, and we have not yet reached the maximum
  824.     // allowable size for a base, reallocate a larger base and rehash
  825.     // the elements.
  826.     //
  827.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  828.         Rehash();
  829.  
  830.     return lit;
  831. }
  832.  
  833.  
  834. LongInt LongLiteralTable::int64_limit = LongInt(0x7FFFFFFF, 0xFFFFFFFF) / 10;
  835. int LongLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  836.  
  837. LongLiteralTable::LongLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  838.                                                                hash_size(primes[0]),
  839.                                                                prime_index(0),
  840.                                                                bad_value(bad_value_)
  841. {
  842.     base = (LongLiteralValue **) memset(new LongLiteralValue *[hash_size], 0, hash_size * sizeof(LongLiteralValue *));
  843.     symbol_pool.Next() = NULL; // do not use the 0th element
  844. }
  845.  
  846. LongLiteralTable::~LongLiteralTable()
  847. {
  848. /*
  849. int n;
  850. int num_slots = 0;
  851. int total = 0;
  852. for (n = 0; n < hash_size; n++)
  853. {
  854. int num = 0;
  855. for (LiteralValue *s = base[n]; s; s = s -> next)
  856.     num++;
  857. if (num > 0)
  858. {
  859. num_slots++;
  860. total += num;
  861. }
  862. }
  863.  
  864. if (num_slots > 0)
  865. {
  866. Coutput << "\nDestroying the long table with " << total
  867.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  868. for (n = 0; n < hash_size; n++)
  869. {
  870. int num = 0;
  871. for (LiteralValue *s = base[n]; s; s = s -> next)
  872.     num++;
  873. if (num > 0)
  874. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  875. }
  876. }
  877. if (hash_size < total)
  878.     total = total;
  879. */
  880.  
  881. #ifdef TEST
  882.     for (int i = 0; i < symbol_pool.Length(); i++)
  883.         delete symbol_pool[i];
  884.     delete [] base;
  885. #endif
  886. }
  887.  
  888.  
  889. LiteralValue *LongLiteralTable::FindOrInsertHexLong(LiteralSymbol *literal)
  890. {
  891.     u4 high = 0,
  892.        low = 0;
  893.  
  894.     wchar_t *head = literal -> Name() + 1, // point to X
  895.             *tail = &literal -> Name()[literal -> NameLength() - 2]; // -2 to skip the 'L' suffix
  896.  
  897.     //
  898.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  899.     // hexadecimal or octal int literal does not fit in 32 bits".
  900.     // So, strictly speaking, we should not skip leading zeroes. However,
  901.     // there are many publicly available code out there with leading zeroes
  902.     // that don't compile with jikes,...
  903.     //
  904.     {
  905.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  906.             ;
  907.         head--;
  908.     }
  909.  
  910.     for (int i = 0; i < 32 && tail > head; i += 4, tail--)
  911.     {
  912.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  913.         low |= (d << i);
  914.     }
  915.  
  916.     for (int j = 0; j < 32 && tail > head; j += 4, tail--)
  917.     {
  918.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  919.         high |= (d << j);
  920.     }
  921.  
  922.     return (tail > head ? bad_value : FindOrInsert(LongInt(high, low)));
  923. }
  924.  
  925.  
  926. LiteralValue *LongLiteralTable::FindOrInsertOctalLong(LiteralSymbol *literal)
  927. {
  928.     wchar_t *head = literal -> Name(), // point to initial '0'
  929.             *tail = &head[literal -> NameLength() - 2]; // -2 to skip the 'L' suffix
  930.  
  931.     ULongInt uvalue = 0;
  932.     //
  933.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  934.     // hexadecimal or octal int literal does not fit in 32 bits".
  935.     // So, strictly speaking, we should not skip leading zeroes. However,
  936.     // there are many publicly available code out there with leading zeroes
  937.     // that wouldn't otherwise compile with jikes,...
  938.     //
  939.     {
  940.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  941.             ;
  942.         head--;
  943.     }
  944.  
  945.     for (int i = 0; i < 63 && tail > head; i += 3, tail--)
  946.     {
  947.         ULongInt d = (u4) (*tail - U_0);
  948.         uvalue |= (d << i);
  949.     }
  950.  
  951.     if (tail > head)
  952.     {
  953.         u4 d = *tail - U_0;
  954.  
  955.         if (d <= 1) // max number that can fit in 1 bit
  956.         {
  957.             tail--;
  958.             uvalue |= ULongInt((d << 31), 0);
  959.         }
  960.     }
  961.  
  962.     return (tail > head ? bad_value : FindOrInsert((LongInt) uvalue));
  963. }
  964.  
  965.  
  966. LiteralValue *LongLiteralTable::FindOrInsertLong(LiteralSymbol *literal)
  967. {
  968.     wchar_t *name = literal -> Name();
  969.  
  970.     //
  971.     // We can assert that the name of a literal contains at least two characters:
  972.     // at least one digit and the terminating '\0'.
  973.     //
  974.     if (name[0] == U_0)
  975.         literal -> value = (name[1] == U_x || name[1] == U_X ? FindOrInsertHexLong(literal) : FindOrInsertOctalLong(literal));
  976.     else
  977.     {
  978.         LongInt value = 0;
  979.  
  980.         wchar_t *p;
  981.         for (p = name; *p != U_L && *p != U_l; p++)
  982.         {
  983.             u4 digit = *p - U_0;
  984.             if (value > int64_limit || (value == int64_limit && digit > 7))
  985.                 break;
  986.             value = value * 10 + digit;
  987.         }
  988.  
  989.         literal -> value = (*p != U_L && *p != U_l ? bad_value : FindOrInsert(value));
  990.     }
  991.  
  992.     return literal -> value;
  993. }
  994.  
  995.  
  996. LiteralValue *LongLiteralTable::FindOrInsertNegativeLong(LiteralSymbol *literal)
  997. {
  998.     if (literal -> value && literal -> value != bad_value) // a positive value already exists
  999.     {
  1000.         LongLiteralValue *long_literal = (LongLiteralValue *) literal -> value;
  1001.         return FindOrInsert(- long_literal -> value);
  1002.     }
  1003.  
  1004.     wchar_t *name = literal -> Name();
  1005.     //
  1006.     // We can assert that the name of a literal contains at least two characters:
  1007.     // at least one digit and the terminating '\0'.
  1008.     //
  1009.     if (name[0] == U_0)
  1010.     {
  1011.         LongLiteralValue *long_literal = (LongLiteralValue *) (name[1] == U_x || name[1] == U_X
  1012.                                                                                ? FindOrInsertHexLong(literal)
  1013.                                                                                : FindOrInsertOctalLong(literal));
  1014.         return FindOrInsert(- long_literal -> value);
  1015.     }
  1016.  
  1017.     LongInt value = 0;
  1018.  
  1019.     wchar_t *p;
  1020.     for (p = name; *p != U_L && *p != U_l && value >= 0; p++)
  1021.     {
  1022.         u4 digit = *p - U_0;
  1023.         if (value > int64_limit || (value == int64_limit && digit > 8))
  1024.             break;
  1025.         value = value * 10 + digit;
  1026.     }
  1027.  
  1028.     return (*p != U_L && *p != U_l ? bad_value : FindOrInsert(-value));
  1029. }
  1030.  
  1031.  
  1032. void LongLiteralTable::Rehash()
  1033. {
  1034.     hash_size = primes[++prime_index];
  1035.  
  1036.     delete [] base;
  1037.     base = (LongLiteralValue **) memset(new LongLiteralValue *[hash_size], 0, hash_size * sizeof(LongLiteralValue *));
  1038.  
  1039.     //
  1040.     // Recall that the 0th element is unused.
  1041.     //
  1042.     for (int i = 1; i < symbol_pool.Length(); i++)
  1043.     {
  1044.         LongLiteralValue *llv = symbol_pool[i];
  1045.         int k = (((ULongInt) llv -> value) % ULongInt(0, hash_size)).LowWord(); // The ULongInt turns negative values positive
  1046.         llv -> next = base[k];
  1047.         base[k] = llv;
  1048.     }
  1049.  
  1050.     return;
  1051. }
  1052.  
  1053.  
  1054. LongLiteralValue *LongLiteralTable::FindOrInsert(LongInt value)
  1055. {
  1056.     int k = (((ULongInt) value) % ULongInt(0, hash_size)).LowWord();  // The ULongInt cast turns negative values into positive values
  1057.  
  1058.     LongLiteralValue *lit;
  1059.     for (lit = base[k]; lit; lit = (LongLiteralValue *) lit -> next)
  1060.     {
  1061.         if (lit -> value == value)
  1062.             return lit;
  1063.     }
  1064.  
  1065.     lit = new LongLiteralValue();
  1066.     lit -> Initialize(value, symbol_pool.Length());
  1067.     symbol_pool.Next() = lit;
  1068.  
  1069.     lit -> next = base[k];
  1070.     base[k] = lit;
  1071.  
  1072.     //
  1073.     // If the number of unique elements in the hash table exceeds 2 times
  1074.     // the size of the base, and we have not yet reached the maximum
  1075.     // allowable size for a base, reallocate a larger base and rehash
  1076.     // the elements.
  1077.     //
  1078.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1079.         Rehash();
  1080.  
  1081.     return lit;
  1082. }
  1083.  
  1084.  
  1085. int FloatLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1086.  
  1087. FloatLiteralTable::FloatLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1088.                                                                  hash_size(primes[0]),
  1089.                                                                  prime_index(0),
  1090.                                                                  bad_value(bad_value_)
  1091. {
  1092.     base = (FloatLiteralValue **) memset(new FloatLiteralValue *[hash_size], 0, hash_size * sizeof(FloatLiteralValue *));
  1093.     symbol_pool.Next() = NULL; // do not use the 0th element
  1094. }
  1095.  
  1096. FloatLiteralTable::~FloatLiteralTable()
  1097. {
  1098. /*
  1099. int n;
  1100. int num_slots = 0;
  1101. int total = 0;
  1102. for (n = 0; n < hash_size; n++)
  1103. {
  1104. int num = 0;
  1105. for (LiteralValue *s = base[n]; s; s = s -> next)
  1106.     num++;
  1107. if (num > 0)
  1108. {
  1109. num_slots++;
  1110. total += num;
  1111. }
  1112. }
  1113.  
  1114. if (num_slots > 0)
  1115. {
  1116. Coutput << "\nDestroying the float table with " << total
  1117.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1118. for (n = 0; n < hash_size; n++)
  1119. {
  1120. int num = 0;
  1121. for (LiteralValue *s = base[n]; s; s = s -> next)
  1122.     num++;
  1123. if (num > 0)
  1124. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1125. }
  1126. }
  1127. if (hash_size < total)
  1128.     total = total;
  1129. */
  1130.  
  1131. #ifdef TEST
  1132.     for (int i = 0; i < symbol_pool.Length(); i++)
  1133.         delete symbol_pool[i];
  1134.     delete [] base;
  1135. #endif
  1136. }
  1137.  
  1138.  
  1139. LiteralValue *FloatLiteralTable::FindOrInsertFloat(LiteralSymbol *literal)
  1140. {
  1141.     char *name = new char[literal -> NameLength() + 1];
  1142.     for (size_t i = 0; i < literal -> NameLength(); i++)
  1143.         name[i] = (char) literal -> Name()[i];
  1144.     name[literal -> NameLength()] = U_NULL;
  1145.  
  1146.     IEEEfloat value = IEEEfloat(name);
  1147.  
  1148.     literal -> value = FindOrInsert(value);
  1149.  
  1150.     delete [] name;
  1151.  
  1152.     return literal -> value;
  1153. }
  1154.  
  1155.  
  1156. void FloatLiteralTable::Rehash()
  1157. {
  1158.     hash_size = primes[++prime_index];
  1159.  
  1160.     delete [] base;
  1161.     base = (FloatLiteralValue **) memset(new FloatLiteralValue *[hash_size], 0, hash_size * sizeof(FloatLiteralValue *));
  1162.  
  1163.     //
  1164.     // Recall that the 0th element is unused.
  1165.     //
  1166.     for (int i = 1; i < symbol_pool.Length(); i++)
  1167.     {
  1168.         FloatLiteralValue *flv = symbol_pool[i];
  1169.         int k = Hash(flv -> value) % hash_size; // the hash function for float values is cheap so we don't need to save it.
  1170.         flv -> next = base[k];
  1171.         base[k] = flv;
  1172.     }
  1173.  
  1174.     return;
  1175. }
  1176.  
  1177.  
  1178. FloatLiteralValue *FloatLiteralTable::FindOrInsert(IEEEfloat value)
  1179. {
  1180.     int k = Hash(value) % hash_size;
  1181.  
  1182.     FloatLiteralValue *lit;
  1183.     for (lit = base[k]; lit; lit = (FloatLiteralValue *) lit -> next)
  1184.     {
  1185.         if (lit -> value == value)
  1186.             return lit;
  1187.     }
  1188.  
  1189.     lit = new FloatLiteralValue();
  1190.     lit -> Initialize(value, symbol_pool.Length());
  1191.     symbol_pool.Next() = lit;
  1192.  
  1193.     lit -> next = base[k];
  1194.     base[k] = lit;
  1195.  
  1196.     //
  1197.     // If the number of unique elements in the hash table exceeds 2 times
  1198.     // the size of the base, and we have not yet reached the maximum
  1199.     // allowable size for a base, reallocate a larger base and rehash
  1200.     // the elements.
  1201.     //
  1202.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1203.         Rehash();
  1204.  
  1205.     return lit;
  1206. }
  1207.  
  1208.  
  1209. int DoubleLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1210.  
  1211. DoubleLiteralTable::DoubleLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1212.                                                                    hash_size(primes[0]),
  1213.                                                                    prime_index(0),
  1214.                                                                    bad_value(bad_value_)
  1215. {
  1216.     base = (DoubleLiteralValue **) memset(new DoubleLiteralValue *[hash_size], 0, hash_size * sizeof(DoubleLiteralValue *));
  1217.     symbol_pool.Next() = NULL; // do not use the 0th element
  1218. }
  1219.  
  1220. DoubleLiteralTable::~DoubleLiteralTable()
  1221. {
  1222. /*
  1223. int n;
  1224. int num_slots = 0;
  1225. int total = 0;
  1226. for (n = 0; n < hash_size; n++)
  1227. {
  1228. int num = 0;
  1229. for (LiteralValue *s = base[n]; s; s = s -> next)
  1230.     num++;
  1231. if (num > 0)
  1232. {
  1233. num_slots++;
  1234. total += num;
  1235. }
  1236. }
  1237.  
  1238. if (num_slots > 0)
  1239. {
  1240. Coutput << "\nDestroying the double table with " << total
  1241.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1242. for (n = 0; n < hash_size; n++)
  1243. {
  1244. int num = 0;
  1245. for (LiteralValue *s = base[n]; s; s = s -> next)
  1246.     num++;
  1247. if (num > 0)
  1248. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1249. }
  1250. }
  1251. if (hash_size < total)
  1252.     total = total;
  1253. */
  1254. #ifdef TEST
  1255.     for (int i = 0; i < symbol_pool.Length(); i++)
  1256.         delete symbol_pool[i];
  1257.     delete [] base;
  1258. #endif
  1259. }
  1260.  
  1261.  
  1262. LiteralValue *DoubleLiteralTable::FindOrInsertDouble(LiteralSymbol *literal)
  1263. {
  1264.     char *name = new char[literal -> NameLength() + 1];
  1265.     for (size_t i = 0; i < literal -> NameLength(); i++)
  1266.         name[i] = (char) literal -> Name()[i];
  1267.     name[literal -> NameLength()] = U_NULL;
  1268.  
  1269.     IEEEdouble value = IEEEdouble(name);
  1270.  
  1271.     literal -> value = FindOrInsert(value);
  1272.  
  1273.     delete [] name;
  1274.  
  1275.     return literal -> value;
  1276. }
  1277.  
  1278.  
  1279. void DoubleLiteralTable::Rehash()
  1280. {
  1281.     hash_size = primes[++prime_index];
  1282.  
  1283.     delete [] base;
  1284.     base = (DoubleLiteralValue **) memset(new DoubleLiteralValue *[hash_size], 0, hash_size * sizeof(DoubleLiteralValue *));
  1285.  
  1286.     //
  1287.     // Recall that the 0th element is unused.
  1288.     //
  1289.     for (int i = 1; i < symbol_pool.Length(); i++)
  1290.     {
  1291.         DoubleLiteralValue *dlv = symbol_pool[i];
  1292.         int k = Hash(dlv -> value) % hash_size; // the hash function for double values is cheap so we don't need to save it.
  1293.         dlv -> next = base[k];
  1294.         base[k] = dlv;
  1295.     }
  1296.  
  1297.     return;
  1298. }
  1299.  
  1300.  
  1301. DoubleLiteralValue *DoubleLiteralTable::FindOrInsert(IEEEdouble value)
  1302. {
  1303.     int k = Hash(value) % hash_size;
  1304.  
  1305.     DoubleLiteralValue *lit;
  1306.     for (lit = base[k]; lit; lit = (DoubleLiteralValue *) lit -> next)
  1307.     {
  1308.         if (lit -> value == value)
  1309.             return lit;
  1310.     }
  1311.  
  1312.     lit = new DoubleLiteralValue();
  1313.     lit -> Initialize(value, symbol_pool.Length());
  1314.     symbol_pool.Next() = lit;
  1315.  
  1316.     lit -> next = base[k];
  1317.     base[k] = lit;
  1318.  
  1319.     //
  1320.     // If the number of unique elements in the hash table exceeds 2 times
  1321.     // the size of the base, and we have not yet reached the maximum
  1322.     // allowable size for a base, reallocate a larger base and rehash
  1323.     // the elements.
  1324.     //
  1325.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1326.         Rehash();
  1327.  
  1328.     return lit;
  1329. }
  1330.  
  1331.  
  1332. LiteralValue *Utf8LiteralTable::FindOrInsertString(LiteralSymbol *literal)
  1333. {
  1334.     wchar_t *name = literal -> Name();
  1335.  
  1336.     int literal_length = literal -> NameLength();
  1337.  
  1338.     char *value = new char[literal_length * 3]; // should be big enough for the worst case
  1339.     int len = 0,
  1340.         i;
  1341.     for (i = 1; i < literal_length && name[i] != U_DOUBLE_QUOTE; i++)  // start at 1 to skip the initial \"
  1342.     {
  1343.         int ch = name[i];
  1344.  
  1345.         if (ch == U_BACKSLASH)
  1346.         {
  1347.             if (name[i + 1] == U_b)
  1348.             {
  1349.                 i++;
  1350.                 ch = U_BACKSPACE;
  1351.             }
  1352.             else if (name[i + 1] == U_t)
  1353.             {
  1354.                 i++;
  1355.                 ch = U_HORIZONTAL_TAB;
  1356.             }
  1357.             else if (name[i + 1] == U_n)
  1358.             {
  1359.                 i++;
  1360.                 ch = U_LINE_FEED;
  1361.             }
  1362.             else if (name[i + 1] == U_f)
  1363.             {
  1364.                 i++;
  1365.                 ch = U_FORM_FEED;
  1366.             }
  1367.             else if (name[i + 1] == U_r)
  1368.             {
  1369.                 i++;
  1370.                 ch = U_CARRIAGE_RETURN;
  1371.             }
  1372.             else if (name[i + 1] == U_DOUBLE_QUOTE)
  1373.             {
  1374.                 i++;
  1375.                 ch = U_DOUBLE_QUOTE;
  1376.             }
  1377.             else if (name[i + 1] == U_SINGLE_QUOTE)
  1378.             {
  1379.                 i++;
  1380.                 ch = U_SINGLE_QUOTE;
  1381.             }
  1382.             else if (name[i + 1] == U_BACKSLASH)
  1383.             {
  1384.                 i++;
  1385.                 ch = U_BACKSLASH;
  1386.             }
  1387.             else if (Code::IsDigit(name[i + 1]))
  1388.             {
  1389.                 int digit = name[++i] - U_0;
  1390.  
  1391.                 if (digit > 7) // The first digit must be an octal digit
  1392.                     ch = -1;
  1393.                 else
  1394.                 {
  1395.                     ch = digit;
  1396.                     if (Code::IsDigit(name[i + 1]))
  1397.                     {
  1398.                         digit = name[i + 1] - U_0;
  1399.                         if (digit < 8)
  1400.                         {
  1401.                             ch = ch * 8 + digit;
  1402.                             i++;
  1403.                             if (Code::IsDigit(name[i + 1]))
  1404.                             {
  1405.                                 digit = name[i + 1] - U_0;
  1406.                                 if (ch <= 0x1F && digit < 8)
  1407.                                 {
  1408.                                     ch = ch * 8 + digit;
  1409.                                     i++;
  1410.                                 }
  1411.                             }
  1412.                         }
  1413.                     }
  1414.                 }
  1415.             }
  1416.             else ch = -1;
  1417.         }
  1418.  
  1419.         if (ch < 0)
  1420.              break;
  1421.         else if (ch == 0)
  1422.         {
  1423.              value[len++] = (char) 0xC0;
  1424.              value[len++] = (char) 0x80;
  1425.         }
  1426.         else if (ch <= 0x007F)
  1427.              value[len++] = (char) ch;
  1428.         else if (ch <= 0x07FF)
  1429.         {
  1430.              value[len++] = (char) ((char) 0xC0 | (char) ((ch >> 6) & 0x001F)); // bits 6-10
  1431.              value[len++] = (char) ((char) 0x80 | (char) (ch & 0x003F));        // bits 0-5
  1432.         }
  1433.         else
  1434.         {
  1435.              value[len++] = (char) ((char) 0xE0 | (char) ((ch >> 12) & 0x000F));
  1436.              value[len++] = (char) ((char) 0x80 | (char) ((ch >> 6) & 0x003F));
  1437.              value[len++] = (char) ((char) 0x80 | (char) (ch & 0x3F));
  1438.         }
  1439.     }
  1440.  
  1441.     value[len] = U_NULL;
  1442.     literal -> value = (i < literal_length && name[i] != U_DOUBLE_QUOTE ? bad_value : FindOrInsert(value, len));
  1443.  
  1444.     delete [] value;
  1445.     return literal -> value;
  1446. }
  1447.  
  1448.  
  1449. Utf8LiteralValue *Utf8LiteralTable::FindOrInsert(wchar_t ch)
  1450. {
  1451.     int len = 0;
  1452.     char str[4];
  1453.  
  1454.     if (ch == 0)
  1455.     {
  1456.          str[len++] = (char) 0xC0;
  1457.          str[len++] = (char) 0x80;
  1458.     }
  1459.     else if (ch <= 0x007F)
  1460.          str[len++] = (char) ch;
  1461.     else if (ch <= 0x07FF)
  1462.     {
  1463.          str[len++] = (char) ((char) 0xC0 | (char) ((ch >> 6) & 0x001F)); // bits 6-10
  1464.          str[len++] = (char) ((char) 0x80 | (char) (ch & 0x003F));        // bits 0-5
  1465.     }
  1466.     else
  1467.     {
  1468.          str[len++] = (char) ((char) 0xE0 | (char) ((ch >> 12) & 0x000F));
  1469.          str[len++] = (char) ((char) 0x80 | (char) ((ch >> 6) & 0x003F));
  1470.          str[len++] = (char) ((char) 0x80 | (char) (ch & 0x3F));
  1471.     }
  1472.  
  1473.     str[len] = U_NULL;
  1474.  
  1475.     return FindOrInsert(str, len);
  1476. }
  1477.  
  1478.  
  1479. void Utf8LiteralTable::Rehash()
  1480. {
  1481.     hash_size = primes[++prime_index];
  1482.  
  1483.     delete [] base;
  1484.     base = (Utf8LiteralValue **) memset(new Utf8LiteralValue *[hash_size], 0, hash_size * sizeof(Utf8LiteralValue *));
  1485.  
  1486.     //
  1487.     // Recall that the 0th element is unused.
  1488.     //
  1489.     for (int i = 1; i < symbol_pool.Length(); i++)
  1490.     {
  1491.         Utf8LiteralValue *ulv = symbol_pool[i];
  1492.         int k = ulv -> hash_address % hash_size;
  1493.         ulv -> next = base[k];
  1494.         base[k] = ulv;
  1495.     }
  1496.  
  1497.     return;
  1498. }
  1499.  
  1500.  
  1501. int Utf8LiteralTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  1502.  
  1503. Utf8LiteralTable::Utf8LiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1504.                                                                hash_size(primes[0]),
  1505.                                                                prime_index(0),
  1506.                                                                bad_value(bad_value_)
  1507. {
  1508.     base = (Utf8LiteralValue **) memset(new Utf8LiteralValue *[hash_size], 0, hash_size * sizeof(Utf8LiteralValue *));
  1509.     symbol_pool.Next() = NULL; // do not use the 0th element
  1510. }
  1511.  
  1512.  
  1513. Utf8LiteralTable::~Utf8LiteralTable()
  1514. {
  1515. /*
  1516. int n;
  1517. int num_slots = 0;
  1518. int total = 0;
  1519. for (n = 0; n < hash_size; n++)
  1520. {
  1521. int num = 0;
  1522. for (LiteralValue *s = base[n]; s; s = s -> next)
  1523.     num++;
  1524. if (num > 0)
  1525. {
  1526. num_slots++;
  1527. total += num;
  1528. }
  1529. }
  1530.  
  1531. if (num_slots > 0)
  1532. {
  1533. Coutput << "\nDestroying the Utf8 table with " << total
  1534.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1535. for (n = 0; n < hash_size; n++)
  1536. {
  1537. int num = 0;
  1538. for (LiteralValue *s = base[n]; s; s = s -> next)
  1539.     num++;
  1540. if (num > 0)
  1541. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1542. }
  1543. }
  1544. if (hash_size < total)
  1545.     total = total;
  1546. */
  1547. #ifdef TEST
  1548.     for (int i = 0; i < symbol_pool.Length(); i++)
  1549.         delete symbol_pool[i];
  1550.     delete [] base;
  1551. #endif
  1552. }
  1553.  
  1554.  
  1555. Utf8LiteralValue *Utf8LiteralTable::FindOrInsert(char *str, int len)
  1556. {
  1557.     unsigned hash_address = Hash(str, len);
  1558.     int k = hash_address % hash_size;
  1559.  
  1560.     Utf8LiteralValue *lit;
  1561.     for (lit = base[k]; lit; lit = (Utf8LiteralValue *) lit -> next)
  1562.     {
  1563.         if (len == lit -> length)
  1564.         {
  1565.             if (memcmp(lit -> value, str, len * sizeof(char)) == 0)
  1566.                  return lit;
  1567.         }
  1568.     }
  1569.  
  1570.     lit = new Utf8LiteralValue();
  1571.     lit -> Initialize(str, len, hash_address, symbol_pool.Length());
  1572.     symbol_pool.Next() = lit;
  1573.  
  1574.     lit -> next = base[k];
  1575.     base[k] = lit;
  1576.  
  1577.     //
  1578.     // If the number of unique elements in the hash table exceeds 2 times
  1579.     // the size of the base, and we have not yet reached the maximum
  1580.     // allowable size for a base, reallocate a larger base and rehash
  1581.     // the elements.
  1582.     //
  1583.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1584.         Rehash();
  1585.  
  1586.     return lit;
  1587. }
  1588.  
  1589.  
  1590. void Utf8LiteralTable::EvaluateConstant(AstExpression *expression, int start, int end)
  1591. {
  1592.     if (end - start > 1)
  1593.     {
  1594.         int length = 0;
  1595.         for (int i = start; i < end; i++)
  1596.         {
  1597.             Utf8LiteralValue *literal = (Utf8LiteralValue *) (*expr)[i] -> value;
  1598.             length += literal -> length;
  1599.         }
  1600.         char *str = new char[length + 1]; // +1 for '\0'
  1601.  
  1602.         int index = 0;
  1603.         for (int k = start; k < end; k++)
  1604.         {
  1605.             Utf8LiteralValue *literal = (Utf8LiteralValue *) (*expr)[k] -> value;
  1606.  
  1607.             assert(literal -> value);
  1608.  
  1609.             memmove(&str[index], literal -> value, literal -> length * sizeof(char));
  1610.             index += literal -> length;
  1611.         }
  1612.         str[length] = U_NULL;
  1613.  
  1614.         expression -> value = FindOrInsert(str, length);
  1615.  
  1616.         delete [] str;
  1617.     }
  1618.     return;
  1619. }
  1620.  
  1621.  
  1622. bool Utf8LiteralTable::IsConstant(AstExpression *expression)
  1623. {
  1624.     if (expression -> IsConstant())
  1625.     {
  1626.         expr -> Next() = expression;
  1627.         return true;
  1628.     }
  1629.  
  1630.     AstBinaryExpression *binary_expression;
  1631.     AstCastExpression *cast_expression;
  1632.     AstParenthesizedExpression *parenthesized_expression;
  1633.     if ((binary_expression = expression -> BinaryExpressionCast()))
  1634.     {
  1635.         int left_start_marker = expr -> Length();
  1636.  
  1637.         AstExpression *left  = binary_expression -> left_expression,
  1638.                       *right = binary_expression -> right_expression;
  1639.  
  1640.         bool left_is_constant = IsConstant(left);
  1641.  
  1642.         int left_end_marker = expr -> Length();
  1643.  
  1644.         bool right_is_constant = IsConstant(right);
  1645.         if (left_is_constant && right_is_constant)
  1646.              return true;
  1647.  
  1648.         if (left_is_constant)
  1649.              EvaluateConstant(left, left_start_marker, left_end_marker);
  1650.         else if (right_is_constant)
  1651.              EvaluateConstant(right, left_end_marker, expr -> Length());
  1652.  
  1653.         expr -> Reset(left_start_marker);
  1654.     }
  1655.     else if ((cast_expression = expression -> CastExpressionCast()))
  1656.          return IsConstant(cast_expression -> expression);
  1657.     else if ((parenthesized_expression = expression -> ParenthesizedExpressionCast()))
  1658.          return IsConstant(parenthesized_expression -> expression);
  1659.  
  1660.     return false; // Not a constant String expression
  1661. }
  1662.  
  1663.  
  1664.  
  1665. void Utf8LiteralTable::CheckStringConstant(AstExpression *expression)
  1666. {
  1667.     expr = new Tuple<AstExpression *>(256);
  1668.  
  1669.     if (IsConstant(expression))
  1670.         EvaluateConstant(expression, 0, expr -> Length());
  1671.  
  1672.     delete expr;
  1673.  
  1674.     return;
  1675. }
  1676.  
  1677.  
  1678. int LiteralLookupTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1679.  
  1680. LiteralLookupTable::LiteralLookupTable() : symbol_pool(16384),
  1681.                                            hash_size(primes[0]),
  1682.                                            prime_index(0)
  1683. {
  1684.     base = (LiteralSymbol **) memset(new LiteralSymbol *[hash_size], 0, hash_size * sizeof(LiteralSymbol *));
  1685. }
  1686.  
  1687. LiteralLookupTable::~LiteralLookupTable()
  1688. {
  1689. /*
  1690. int n;
  1691. int num_slots = 0;
  1692. int total = 0;
  1693. for (n = 0; n < hash_size; n++)
  1694. {
  1695. int num = 0;
  1696. for (Symbol *s = base[n]; s; s = s -> next)
  1697.     num++;
  1698. if (num > 0)
  1699. {
  1700. num_slots++;
  1701. total += num;
  1702. }
  1703. }
  1704.  
  1705. if (num_slots > 0)
  1706. {
  1707. Coutput << "\nDestroying the Literal table with " << total
  1708.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1709. for (n = 0; n < hash_size; n++)
  1710. {
  1711. int num = 0;
  1712. for (Symbol *s = base[n]; s; s = s -> next)
  1713.     num++;
  1714. if (num > 0)
  1715. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1716. }
  1717. }
  1718. if (hash_size < total)
  1719.     total = total;
  1720. */
  1721. #ifdef TEST
  1722.     for (int i = 0; i < symbol_pool.Length(); i++)
  1723.         delete symbol_pool[i];
  1724.     delete [] base;
  1725. #endif
  1726. }
  1727.  
  1728.  
  1729. void LiteralLookupTable::Rehash()
  1730. {
  1731.     hash_size = primes[++prime_index];
  1732.  
  1733.     delete [] base;
  1734.     base = (LiteralSymbol **) memset(new LiteralSymbol *[hash_size], 0, hash_size * sizeof(LiteralSymbol *));
  1735.  
  1736.     for (int i = 0; i < symbol_pool.Length(); i++)
  1737.     {
  1738.         LiteralSymbol *ls = symbol_pool[i];
  1739.         int k = ls -> hash_address % hash_size;
  1740.         ls -> next = base[k];
  1741.         base[k] = ls;
  1742.     }
  1743.  
  1744.     return;
  1745. }
  1746.  
  1747.  
  1748. LiteralSymbol *LiteralLookupTable::FindOrInsertLiteral(wchar_t *str, size_t len)
  1749. {
  1750.     unsigned hash_address = Hash(str, len);
  1751.     int k = hash_address % hash_size;
  1752.     LiteralSymbol *symbol;
  1753.     for (symbol = base[k]; symbol; symbol = (LiteralSymbol *) symbol -> next)
  1754.     {
  1755.         if (len == symbol -> NameLength() && memcmp(symbol -> Name(), str, len * sizeof(wchar_t)) == 0)
  1756.             return symbol;
  1757.     }
  1758.  
  1759.     symbol = new LiteralSymbol();
  1760.     symbol_pool.Next() = symbol;
  1761.     symbol -> Initialize(str, hash_address, len);
  1762.  
  1763.     symbol -> next = base[k];
  1764.     base[k] = symbol;
  1765.  
  1766.     //
  1767.     // If the number of unique elements in the hash table exceeds 2 times
  1768.     // the size of the base, and we have not yet reached the maximum
  1769.     // allowable size for a base, reallocate a larger base and rehash
  1770.     // the elements.
  1771.     //
  1772.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1773.         Rehash();
  1774.  
  1775.     return symbol;
  1776. }
  1777.